class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        l = 0
        r = 0
        need = {}
        res = ""
        #初始化需要满足的需求
        total_cnt = 0
        for c in t:
            need[c] = need.get(c, 0) + 1
        #统计需要的字符数
        needCnt = len(t)

        for r in range(len(s)):
            #扩大窗口直至满足条件
            if s[r] in need:
                #若当前需要s[r]，添加时则needCnt减小
                if need[s[r]] > 0:
                    needCnt -= 1

                need[s[r]] = need.get(s[r]) - 1
                #total_cnt统计计数<=0的字母个数
                    
            #满足条件则缩小左边界
            while l <= r and needCnt == 0:
                if len(res) == 0  or len(res) > (r - l + 1):
                    res = s[l:r+1]
                
                if s[l] in need:
                    #当前需要s[l],移出时则needCnt+1
                    if need[s[l]] >= 0:
                        needCnt += 1
                    need[s[l]] += 1                   
                l += 1
        return res
